// Copyright 2006 Mloofle Inc. All Rights Reserved.
import java.util.BitSet;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class LineInfo {

  private static final int STRONG_BPE = 10;
  private static final int WEAK_BPE = 6;

  private static BitSet makeBloomFilter(Set wordSet, final int bitsPerElem,
      final int hashCount) {
    final int nElem = wordSet.size();
    final int minBits = nElem * bitsPerElem;

    // round minBits up to power of 2
    int nBits = 1;
    while (nBits < minBits) {
      nBits <<= 1;
    }
    BitSet bitSet = new MyBitSet(nBits);

    // insert all words
    for (Iterator it = wordSet.iterator(); it.hasNext();) {
      String word = (String) it.next();
      int[] hashes = Hasher.computeHashes(word, hashCount);
      for (int i = 0; i < hashCount; ++i) {
        bitSet.set(hashes[i] & (nBits - 1));
      }
    }

    return bitSet;
  }

  public void add(String word) {
    wordList.addLast(word);
  }

  public List generateBloomFilters() {
    LinkedList results = new LinkedList();
    boolean firstPass = true;
    while (!wordList.isEmpty()) {
      // Take one of every word remaining in the list into a set
      Set thisPass = new HashSet();
      // Leave all duplicates for the next pass
      LinkedList nextPass = new LinkedList();
      for (Iterator it = wordList.iterator(); it.hasNext();) {
        String word = (String) it.next();
        if (thisPass.contains(word)) {
          nextPass.addLast(word);
        } else {
          thisPass.add(word);
        }
      }
      // Now compute the bloom filter on the current pass
      BitSet bloomFilter;
      if (firstPass) {
        bloomFilter = makeBloomFilter(thisPass, STRONG_BPE, Util.STRONG_HASHES);
        firstPass = false;
      } else {
        // less accuracy is needed on later passes
        bloomFilter = makeBloomFilter(thisPass, WEAK_BPE, Util.WEAK_HASHES);
      }
      results.addLast(bloomFilter);
      // Update for the next cycle
      wordList = nextPass;
    }
    return results;
  }

  private LinkedList wordList = new LinkedList();
}
